As is known, “spin locks” are computing locks where threads wait in a loop (e.g., “spin”) until the locks become available. Computing operating systems use spin locks to serialize access to various critical sections when they are very short in duration. When a processor is executing in a critical section, other processors seeking to enter the critical section wait for their turn by implementing a “busy wait,” thereby “spinning” on the lock until the lock is available. Since the wait time to acquire the lock is small compared to the time it takes to incur the cost of two context switches (e.g., one to switch out when the lock is not available and one to switch back in when the lock is available), it is more efficient for processors to simply wait for lock acquisition.
Spin locks are also used for serialization when a processor does not have the context to block, such as when the processor is executing in an interrupted context. When an operating system is hosted as a virtual machine on a hypervisor, spin locks present an even further unique performance problem. Consider, for instance, a symmetrical multiprocessing (SMP) guest that is allocated multiple virtual processors (VCPUs). To illustrate the problems being solved in this invention, assume that the number of VCPUs assigned to the guest exceeds the number of physical processors on the machine. In this scenario, when the hypervisor schedules a specific virtual processor of a specific guest, it is possible that the scheduled VCPU might spend the entire time quantum assigned to the VCPU in busy waiting for a spin lock whose holder may have been earlier descheduled by the same hypervisor. As the processor over-commitment increases, the performance problems become worse as multiple CPU cycles are wasted with little or no forward progress. While this problem has been addressed in the past by “para-virtualizing” guests with kernels variously modified to execute on the hypervisor, recent advances in hardware suggest considerable interest in hosting unmodified operating systems as virtual machines thereby obviating para-virtualization.
In another example, consider a fully virtualized (unmodified) guest assigned three VCPUs. It is hosted on a hardware platform having two physical CPUs and a hypervisor multiplexes all of the VCPUs over the two available physical CPUs. In addition, spin lock hold times include events scheduled by the hypervisor and such can become elongated with the occurrence of certain other events. If a first VCPU holding the spin lock gets preempted in lieu of the second and third VCPUs, the hold time for the lock held by the first VCPU will be extended by the time quantum allocated to all the VCPUs ahead of it. This is further exasperated in situations in which the guest implements a fairness policy when granting the spin locks, e.g., “Ticket Spin Locks.” Broadly, ticket spin locks implement fairness by honoring the order in which VCPUs enter the waiting loop and implement a “first-in first-out” servicing strategy. However, since the hypervisor is unaware of this ticket ordering information, any scheduling decision taken by the hypervisor can result in a pathological situation whereby the lock is free but the VCPU that is scheduled cannot acquire the lock since it is not at the head of the list to acquire the lock.
Accordingly, a need exists for better monitoring spin locks. The need further extends to at least the following: detecting situations in which VCPUs may be burning CPU cycles unnecessarily while spinning on a lock whose holder has been preempted by a hypervisor; implementing virtualization-friendly spin locks in a manner transparent to the guest to allow fully virtualized guests; and addressing specialty situations involving ticketed spin locks. Appreciating “cloud” computing environments and more traditional data centers are not always consistent in their selection of computing platforms, the need should further contemplate spin locks in an agnostic fashion where operating systems and physical hardware vary from one box to the next. Any improvements along such lines should also contemplate good engineering practices, such as simplicity, ease of implementation, unobtrusiveness, stability, etc.